Dear Mrs. and Mr. Forum,

Jaroslav Gurican writes

does LLL-algorithm (or some of modifications) offer possibility to
decide memebship (of some element in Z^n in the given lattice?
I need some bibliography on this topic, if possible.
(I would like to avoid excursions to Preburger arithmetic).

I do not see that the LLL algorithm can be used as a general method to
decide membership in lattices. One could think of adding the element
in question to a lattice basis, reduce the vectors using the LLL algorithm,
and then look at the transformation matrix whether the new vector has been
expressed in terms of the old basis. But if this is not the case then of
course this doesn't prove that the vector is not contained in the lattice.

(On the other hand, I cannot prove that the LLL algorithm cannot be used
to decide membership.)

A possibility of testing membership would be to transform the matrix whose
rows form a lattice basis into diagonal form, and to apply the column
transformations to the element in question; then membership can be read
off easily. The problem with this is the ``entry explosion'' during the
process of diagonalizing the matrix.

Kind regards
Thomas Breuer
(sam@math.rwth-aachen.de)